package com.sicheng.lc.周赛.分类.图论.迷宫or优先队列;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/2 12:07
 */
public class 价格范围内最高排名的K样物品 {
    //https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/

    static int[][] d = {
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
    };

    List<List<Integer>> res = new ArrayList<>(100000);
    PriorityQueue<int[]> path = initHeap();

    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        bfs(grid, pricing, start, k);
        while (!path.isEmpty() && k-- > 0) {
            int[] e = path.poll();
            ArrayList<Integer> list = new ArrayList<>();
            list.add(e[0]);
            list.add(e[1]);
            res.add(list);
        }
        return res;
    }

    // 规则 0 是墙 1是空地
    //距离：定义为从start到一件物品的最短路径需要的步数（较近距离的排名更高）。
    //价格：较低价格的物品有更高优先级，但只考虑在给定范围之内的价格。
    //行坐标：较小行坐标的有更高优先级。
    //列坐标：较小列坐标的有更高优先级。

    private void bfs(int[][] grid, int[] pricing, int[] start, int k) {
        int m = grid.length;
        int n = grid[0].length;
        PriorityQueue<int[]> heap = initHeap();
        // {x,y,l,w}
        int[] s = new int[]{start[0], start[1], 0, grid[start[0]][start[1]]};
        grid[start[0]][start[1]] = 0;
        heap.add(s);

        if (s[3] >= pricing[0] && s[3] <= pricing[1])
            path.offer(s);

        while (!heap.isEmpty()) {
            int[] p = heap.poll();
            for (int[] dd : d) {
                int x = p[0] + dd[0];
                int y = p[1] + dd[1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != 0) {
                    int[] e = {x, y, p[2] + 1, grid[x][y]};
                    heap.add(e);
                    if (grid[x][y] >= pricing[0] && grid[x][y] <= pricing[1]) {
                        path.offer(e);
                    }
                    grid[x][y] = 0;
                }
            }
        }
    }

    private PriorityQueue<int[]> initHeap() {
        return new PriorityQueue<>(10000, (e1, e2) -> {
            if (e1[2] != e2[2]) {
                return e1[2] - e2[2];
            }
            if (e1[3] != e2[3]) {
                return e1[3] - e2[3];
            }
            if (e1[0] != e2[0])
                return e1[0] - e2[0];
            return e1[1] - e2[1];
        }
        );
    }

    public static void main(String[] args) {
        int[][] grid = {
                {1, 2, 0, 1},
                {1, 3, 0, 1},
                {0, 2, 5, 1}};
        int[]
                pricing = {2, 5},
                start = {0, 0};
        int k = 3;

        价格范围内最高排名的K样物品 s = new 价格范围内最高排名的K样物品();
        System.out.println(s.highestRankedKItems(grid, pricing, start, k));
    }
}
